In many packet processing systems, packets are stored in buffers in order to provide queuing to handle bursts of traffic, to provide preferential scheduling for some classes of traffic, etc. There have been two main paradigms for such packet storage: full packet, or some type of scatter/gather where a packet is represented as one or more pointers to the pieces of the packet. The full packet storage approach has some large advantages in simplicity. However, the scatter/gather approach may be more bandwidth efficient in some cases where only a portion of the packet needs to be accessed, or where the packet is received (or transmitted) in pieces (fragmented) and must then be reassembled.
Even in the full-packet system, there is a need for re-assembly of packet fragments due to protocols such as Multilink Point to Point Protocol (MLPPP), Link Fragmentation and Interleaving (LFI), and Frame Relay Forum (FRF) Implementation FRF.12. In both the full-packet and the scatter-gather systems, the packet re-assembly techniques used for implementing these protocols have limited scalability.
For example, in systems that store full packets, only a portion of the packet may be available at any one time or different fragments may arrive in arbitrary orders. When fragments are eventually dequeued, the different portions of the same packet must then be put back together. A large amount of processor bandwidth is required for dynamically tracking and accessing the different pieces of data that make up the reassembled packet.
Thus a need remains for improving the efficiency in which packet-pieces are reassembled into full packets. The present invention addresses this and other problems associated with the prior art.